home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 8576 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.1 KB
  1. Path: garden.csc.calpoly.edu!not-for-mail
  2. From: dstubbs@garden.csc.calpoly.edu (Dan Stubbs)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Sorting algorithm - In search of
  5. Date: 4 Mar 1996 20:18:49 -0800
  6. Organization: Cal Poly, San Luis Obispo
  7. Message-ID: <4hgfb9$8b7@garden.csc.calpoly.edu>
  8. References: <4h4jmq$3bh@news.cis.nctu.edu.tw> <4hat5g$bdq@fohnix.metronet.com> <4hd557$ai2@garden.csc.calpoly.edu> <4hff0pINN9f4@keats.ugrad.cs.ubc.ca>
  9. NNTP-Posting-User: dstubbs@garden.csc.calpoly.edu
  10.  
  11. In article <4hff0pINN9f4@keats.ugrad.cs.ubc.ca>,
  12. Kazimir Kylheku <c2a192@ugrad.cs.ubc.ca> wrote:
  13. >
  14. >Who says that qsort() necessarily uses the quicksort agorithm? 
  15. >
  16. Nobody. qsort can, of course, be implemented using any sort algorithm
  17. However, can you name a single distributed C library that implements
  18. qsort using an algorithm other than some version of quicksort?
  19.  
  20. > >Further, some implementations of qsort do not perform well for certain
  21. >
  22. >You surely mean ``of quicksort''. qsort() is a standard C function that is
  23. >unrelated to the quicksort algorithm.
  24. >
  25.  
  26. No, I mean that some implementations of qsort do not perform well for
  27. certain initial data distributions. For the details of several examples
  28. see Bentley, "Engineering a Sort Function," Software--Practice & Experience,
  29. Nov., 93. 
  30.  
  31. >Does the standard require that qsort() be an incarnation of Hoare's quicksort?
  32. >
  33. No, it certainly does not. However, once again, can you name a single
  34. C library in which the implementation of qsort is based on an algorithm
  35. other than quicksort?
  36.  
  37. >You can't test qsort(), you can only test particular implementations of it. 
  38.  
  39. We certainly agree. 
  40.  
  41. A further note. In Bentley's paper referenced above it states, "In fact,
  42. among a dozen different Unix libraries we found no qsort that could not
  43. easily be driven to quadratic behavior; all wer derived from the Seventh
  44. Edition Unix System (from Bell Labs) or from the 1983 Berkeley function."
  45.  
  46. Thus, although by no means required to do so, these dozen systems implemented
  47. qsort with some variation of quicksort. And, in every case there were
  48. initial data distributions that gave serious performance problems. 
  49.  
  50.